/**
 * 1035. 不相交的线
 * https://leetcode-cn.com/problems/uncrossed-lines/
 */
public class Solutions_1035 {
    public static void main(String[] args) {
//        int[] A = {1, 4, 2}, B = {1, 2, 4};  // output: 2
        int[] A = {2, 5, 1, 2, 5}, B = {10, 5, 2, 1, 5, 2};  // output: 3
//        int[] A = {1, 3, 7, 1, 7, 5}, B = {1, 9, 2, 5, 1};  // output: 2

        int result = maxUncrossedLines(A, B);
        System.out.println(result);
    }

    /**
     * 将题目化简为：求两数组中的最长的公共子序列
     * 根据数组 A = {1, 4, 2}, B = {1, 2, 4}，可以列出动态规划矩阵：
     * dp[][]     1  4  2
     *         0  0  0  0
     *      1  0  1  1  1
     *      2  0  1  1  2
     *      4  0  1  2  2
     *     {1} 可以与 {1} 得到 1 个长度的子序列
     * 那么 {1} 与 {1, 2} 也可以得到 1 个长度的子序列，与 {1, 2, 4} 也可以得到 1 个长度的子序列
     *     {1, 4} 可以与 {1} 得到 1 个长度的子序列
     *     {1, 4} 可以与 {1, 2} 得到 1 个长度的子序列
     *     {1, 4} 可以与 {1, 2, 4} 得到 2 个长度的子序列
     */
    public static int maxUncrossedLines(int[] A, int[] B) {
        int row = A.length, col = B.length;
        // dp[3][2] = 2，表示数组 A 前 3 个元素与数组 B 前 2 个元素匹配，可以得到的最长的公共子序列是 2
        int[][] dp = new int[row + 1][col + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (A[i - 1] == B[j - 1]) {
                    // 可以匹配
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 在原本的计算结果中，选择最优解
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // 取最终计算结果，即数组 A 与数组 B 可以匹配的最长子序列长度
        return dp[row][col];
    }
}
